package leetcode;
/**
 * 5.最长回文子串 (动规)
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 输入：s = "babad"
 * 输出："bab"
 * 输入：s = "cbbd"
 * 输出："bb"
 */
//动态规划
import java.util.Scanner;
public class Num_5 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.next();
        System.out.println(longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        //当长度为1时
        if(s.length() == 1){
            return s;
        }
        //定义动规数组
        //dp[i][j]表示区间在[i, j]上的字符串是否为回文串
        boolean[][] dp = new boolean[s.length()][s.length()];
        //初始化，每单个字符都是回文的
        for(int i = 0; i < s.length(); i++){
            dp[i][i] = true;
        }

        //先枚举字符串的长度，从2开始
        for(int l = 2; l <= s.length(); l++){
            //再确定左区间的索引
            for(int i = 0; i < s.length(); i++){
                //得到右边界索引
                int j = i + l - 1;
                if(j >= s.length()){
                    //右边界越界，则结束内层循环
                    break;
                }
                //此时判断[i, j]区间内的字符串是否为回文串
                //当区间长度为2时
                if(i + 1 == j){
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                }else{
                    //区间长度>=3
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
            }
        }
        //找最长的子串
        int l = 1, retI = 0, retJ = 0;
        for(int i = 0; i < s.length(); i++){
            for(int j = i; j < s.length(); j++){
                if(dp[i][j] && j - i + 1 > l){
                    l = j - i + 1;
                    retI = i;
                    retJ = j;
                }
            }
        }
        return s.substring(retI, retJ + 1);
    }
}
